package problem.year2023.month04


/**
 * @author LiangMu
 * @version $Id: Day23.java, v 0.1 2023年04月27日 19:13 LiangMu Exp $$
 */
class Day23 {
    /**
     * 给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。
     *
     * 按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。
     *
     * 先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
     *
     * 需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。
     *
     * 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
     * 每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
     *
     * 以这种方式布置书架，返回书架整体可能的最小高度。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/filling-bookcase-shelves
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    companion object {
        fun minHeightShelves(books: Array<IntArray>, shelfWidth: Int): Int {
            // 按高度先进行排序
            books.sortBy { it[1] }
            books.reverse()
            // 最高的，肯定能包含最低且最宽的
            var res = 0;
            // 如果已经遍历了，那就设置书的宽高都为0，这样表示这个书不存在了
            val len = books.size
            for (index in 0 until len) {
                val width = books[index][0]
                books[index][0] = 0
                val height = books[index][1]
                if (height == 0) continue
                books[index][1] = 0
                res += height // 必定经历的高度
                var dynamicWidth = shelfWidth - width
                for (index2 in index + 1 until len) {
                    val width2 = books[index2][0]
                    if (dynamicWidth < width2) continue // 超长了，不再考虑范围内
                    dynamicWidth -= width2
                    books[index2][0] = 0
                    books[index2][1] = 0
                }
            }
            return res
        }
    }
}
